#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 环形链表II
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
        {
            return nullptr;
        }
        unordered_set<ListNode *> hash;
        while (head)
        {
            if (hash.count(head))
                return head;
            hash.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

// 有效的括号
class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto x : s)
        {
            if (x == ')')
            {
                if (st.empty() || st.top() != '(')
                    return false;
                st.pop();
            }
            else if (x == '}')
            {
                if (st.empty() || st.top() != '{')
                    return false;
                st.pop();
            }
            else if (x == ']')
            {
                if (st.empty() || st.top() != '[')
                    return false;
                st.pop();
            }
            else
                st.push(x);
        }

        return st.empty();
    }
};

// 单词拆分--动态规划
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> hash;
        for (auto str : wordDict)
        {
            hash.insert(str);
        }
        int n = s.size();
        // dp[i]:表示以i位置为结尾是否可以被拼接
        // j为最后一个单词的起始位置 0 <= j <= i
        // dp[i] = dp[j - 1] && (j ~ i)在字典中
        // j - 1会越界,添加一个虚拟节点
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; i++)
        {
            // 注意这里是j >= 1
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

// 压缩字符串
class Solution
{
public:
    int compress(vector<char>& chars)
    {
        string str;
        int left = 0,right = 0,n = chars.size();
        while(right < n)
        {
            while(right < n && chars[right] == chars[left]) right++;
            str += chars[left];
            if(right - left > 1)
            {
                str += to_string(right - left);
            }
            left = right;
        }
        n = str.size();
        for(int i = 0;i < n;i++)
        {
            chars[i] = str[i];
        }
        return n;
    }
};

// 链表相交
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 使用哈希表
        if(headA == nullptr || headB == nullptr) return nullptr;
        unordered_set<ListNode*> hash;
        ListNode* cur = headA;
        while(cur)
        {
            hash.insert(cur);
            cur = cur->next;
        }
        cur = headB;
        while(cur)
        {
            if(hash.count(cur)) return cur;
            cur = cur->next;
        }

        return nullptr;
    }
};

